package com.zp.self.module.level_4_算法练习.数据结构.String;

/**
 * @author By ZengPeng
 */
public class 力扣_696_计数二进制子串 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_696_计数二进制子串().countBinarySubstrings("00110011"));
    }

    /**
    题目：给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，
     并且这些子字符串中的所有 0 和所有 1 都是成组连续的。
     重复出现（不同位置）的子串也要统计它们出现的次数。
      
     示例 1：
     输入：s = "00110011"
     输出：6
     解释：6 个子串满足具有相同数量的连续 1 和 0 ："0011"、"01"、"1100"、"10"、"0011" 和 "01" 。
     注意，一些重复出现的子串（不同位置）要统计它们出现的次数。
     另外，"00110011" 不是有效的子串，因为所有的 0（还有 1 ）没有组合在一起。

     示例 2：
     输入：s = "10101"
     输出：4
     解释：有 4 个子串："10"、"01"、"10"、"01" ，具有相同数量的连续 1 和 0 。

    分析：【P 💜💜💜】
       1.双指针：遍历每个下标，每个下标为起点时，只会出现0，1 能否构成目标字符串
                找到中间变更点，然后向左右扩张？ 注意判断条件
                --执行用时：8 ms, 在所有 Java 提交中击败了86.51%的用户
       官方：我们可以将字符串 s 按照 0 和 1 的连续段分组，存在 ounts 数组中，
               例如 s=00111011，可以得到这样的 counts 数组：counts={2,3,1,2}。
            优化：只记录前面一个

    边界值 & 注意点：
       1.
     **/
    public int countBinarySubstrings(String s) {
        char[] chars = s.toCharArray();
        int left,right=1,sum=0;
        while (right<s.length()){
            if(chars[right]!=chars[right-1]){
                left=right++-2;
                sum++;
                while (left>-1 && right<chars.length
                        && chars[left]!=chars[right] && chars[right]==chars[right-1]){
                    left--;
                    right++;
                    sum++;
                }
            }else
                right++;
        }
        return sum;
    }
}
